| 翻訳と辞書 |
| LCF notation ： ウィキペディア英語版 |
LCF notation
In combinatorial mathematics, LCF notation or LCF code is a notation devised by Joshua Lederberg, and extended by Coxeter and Frucht, for the representation of cubic graphs that contain a Hamiltonian cycle.〔.〕〔.〕
==Description==
In a Hamiltonian graph, the vertices can be arranged in a cycle, which accounts for two edges per vertex. The third edge from each vertex can then be described by how many positions clockwise (positive) or counter-clockwise (negative) it leads. The basic form of the LCF notation is just the sequence of these numbers of positions, starting from an arbitrarily chosen vertex and written in square brackets.
The numbers between the brackets are interpreted modulo ''N'', where ''N'' is the number of vertices. Entries congruent modulo ''N'' to 0, 1, or ''N'' − 1 do not appear in this sequence of numbers,〔Klavdija Kutnar and Dragan Marušič, ("Hamiltonicity of vertex-transitive graphs of order 4''p''," ) ''European Journal of Combinatorics'', Volume 29, Issue 2 (February 2008), pp. 423-438, section 2.〕 because they would correspond either to a loop or multiple adjacency, neither of which are permitted in simple graphs.
Often the pattern repeats, and the number of repetitions can be indicated by a superscript in the notation. For example, the Nauru graph,〔 shown on the right, has four repetitions of the same six offsets, and can be represented by the LCF notation ()4. A single graph may have multiple different LCF notations, depending on the choices of Hamiltonian cycle and starting vertex.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「LCF notation」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|